
public class Algorithms {
    
    // p index begins at 1
    public static int Algorithm1(int[] A, int p, int q) {
        int sum = 0;
        int max = 0;
        
        for (int i = p - 1; i < q; i++) {
            sum = 0;
            
            for (int j = i; j < q; j++) {
                sum += A[j];
                
                if (sum > max) {
                    max = sum;
                }
            }
        }
        
        return max;
    }
    
    // p index begins at 1
    public static int Algorithm2(int[] A, int p, int q) {
        if (p == q) {
            if (A[p - 1] > 0) {
                return A[p - 1];
            }
            else {
                return 0;
            }
        }
        
        int leftPartialSum = 0;
        int rightPartialSum = 0;
        int maxRight = 0;
        int maxLeft = 0;
        int leftMaxSum = 0;
        int rightMaxSum = 0;
        
        int center = (int)Math.floor((p + q) / 2);
        
        maxLeft = Algorithm2(A, p, center);
        maxRight = Algorithm2(A, center + 1, q);
        
        for (int i = center; i >= p; i--) {
            leftPartialSum += A[i - 1];
            
            if (leftPartialSum > leftMaxSum) {
                leftMaxSum = leftPartialSum;
            }
        }
        
        for (int i = center + 1; i <= q; i++) {
            rightPartialSum += A[i - 1];
            
            if (rightPartialSum > rightMaxSum) {
                rightMaxSum = rightPartialSum;
            }
        }
        
        if (maxLeft < maxRight) {
            if (maxRight < (leftMaxSum + rightMaxSum)) {
                return leftMaxSum + rightMaxSum;
            }
            else {
                return maxRight;
            }
        }
        else {
            if (maxRight > (leftMaxSum + rightMaxSum)) {
                return maxLeft;
            }
            else {
                if (maxLeft > (leftMaxSum + rightMaxSum)) {
                    return maxLeft;
                }
                else {
                    return leftMaxSum + rightMaxSum;
                }
            }
        }
    }
    
    // p should begin at index 1
    public static int Algorithm3(int[] A, int p, int q) {
        int sum = 0;
        int max = 0;
        
        for (int i = p - 1; i < q; i++) {
            sum += A[i];
            
            if (sum > max) {
                max = sum;
            }
            else if (sum < 0) {
                sum = 0;
            }
        }
        
        return max;
    }
}
